package com.fasterxml.jackson.databind.deser.std;

import java.io.IOException;
import java.math.BigDecimal;
import java.util.Arrays;

import com.fasterxml.jackson.core.*;
import com.fasterxml.jackson.databind.*;
import com.fasterxml.jackson.databind.cfg.DatatypeFeatures;
import com.fasterxml.jackson.databind.cfg.JsonNodeFeature;
import com.fasterxml.jackson.databind.deser.ContextualDeserializer;
import com.fasterxml.jackson.databind.jsontype.TypeDeserializer;
import com.fasterxml.jackson.databind.node.*;
import com.fasterxml.jackson.databind.type.LogicalType;
import com.fasterxml.jackson.databind.util.RawValue;

/**
 * 添加<code>case JsonTokenId.ID_ENUM:</code>情况
 * <br>
 * 调整 <code>_deserializeContainerNoRecursion</code>处理JsonTokenId.ID_ENUM情况
 */
public class JsonNodeDeserializer extends BaseNodeDeserializer<JsonNode> {

    private final static JsonNodeDeserializer instance = new JsonNodeDeserializer();

    protected JsonNodeDeserializer() {
        super(JsonNode.class, null);
    }

    protected JsonNodeDeserializer(JsonNodeDeserializer base, boolean mergeArrays, boolean mergeObjects) {
        super(base, mergeArrays, mergeObjects);
    }

    @Override
    protected JsonDeserializer<?> _createWithMerge(boolean mergeArrays, boolean mergeObjects) {
        return new JsonNodeDeserializer(this, mergeArrays, mergeObjects);
    }

    public static JsonDeserializer<? extends JsonNode> getDeserializer(Class<?> nodeClass) {
        if (nodeClass == ObjectNode.class) {
            return ObjectDeserializer.getInstance();
        }
        if (nodeClass == ArrayNode.class) {
            return ArrayDeserializer.getInstance();
        }

        return instance;
    }

    @Override
    public JsonNode getNullValue(DeserializationContext ctxt) {
        return ctxt.getNodeFactory().nullNode();
    }

    @Override
    public Object getAbsentValue(DeserializationContext ctxt) {
        return null;
    }

    @Override
    public JsonNode deserialize(JsonParser p, DeserializationContext ctxt) throws IOException {
        final ContainerStack stack = new ContainerStack();
        final JsonNodeFactory nodeF = ctxt.getNodeFactory();
        switch (p.currentTokenId()) {
            case JsonTokenId.ID_START_OBJECT:
                return _deserializeContainerNoRecursion(p, ctxt, nodeF, stack, nodeF.objectNode());
            case JsonTokenId.ID_END_OBJECT:
                return nodeF.objectNode();
            case JsonTokenId.ID_START_ARRAY:
                return _deserializeContainerNoRecursion(p, ctxt, nodeF, stack, nodeF.arrayNode());
            case JsonTokenId.ID_FIELD_NAME:
                return _deserializeObjectAtName(p, ctxt, nodeF, stack);
            default:
        }
        return _deserializeAnyScalar(p, ctxt);
    }

    @Override
    public Boolean supportsUpdate(DeserializationConfig config) {
        return _supportsUpdates;
    }

    final static class ObjectDeserializer extends BaseNodeDeserializer<ObjectNode> {
        private static final long serialVersionUID = 1L;

        protected final static ObjectDeserializer _instance = new ObjectDeserializer();

        protected ObjectDeserializer() {
            super(ObjectNode.class, true);
        }

        public static ObjectDeserializer getInstance() {
            return _instance;
        }

        protected ObjectDeserializer(ObjectDeserializer base, boolean mergeArrays, boolean mergeObjects) {
            super(base, mergeArrays, mergeObjects);
        }

        @Override
        protected JsonDeserializer<?> _createWithMerge(boolean mergeArrays, boolean mergeObjects) {
            return new ObjectDeserializer(this, mergeArrays, mergeObjects);
        }

        @Override
        public ObjectNode deserialize(JsonParser p, DeserializationContext ctxt) throws IOException {
            final JsonNodeFactory nodeF = ctxt.getNodeFactory();
            if (p.isExpectedStartObjectToken()) {
                final ObjectNode root = nodeF.objectNode();
                _deserializeContainerNoRecursion(p, ctxt, nodeF, new ContainerStack(), root);
                return root;
            }
            if (p.hasToken(JsonToken.FIELD_NAME)) {
                return _deserializeObjectAtName(p, ctxt, nodeF, new ContainerStack());
            }
            if (p.hasToken(JsonToken.END_OBJECT)) {
                return nodeF.objectNode();
            }
            return (ObjectNode) ctxt.handleUnexpectedToken(ObjectNode.class, p);
        }

        @Override
        public ObjectNode deserialize(JsonParser p, DeserializationContext ctxt, ObjectNode node) throws IOException {
            if (p.isExpectedStartObjectToken() || p.hasToken(JsonToken.FIELD_NAME)) {
                return (ObjectNode) updateObject(p, ctxt, node, new ContainerStack());
            }
            return (ObjectNode) ctxt.handleUnexpectedToken(ObjectNode.class, p);
        }
    }

    final static class ArrayDeserializer extends BaseNodeDeserializer<ArrayNode> {
        private static final long serialVersionUID = 1L;

        private final static ArrayDeserializer _instance = new ArrayDeserializer();

        private ArrayDeserializer() {
            super(ArrayNode.class, true);
        }

        public static ArrayDeserializer getInstance() {
            return _instance;
        }

        private ArrayDeserializer(ArrayDeserializer base, boolean mergeArrays, boolean mergeObjects) {
            super(base, mergeArrays, mergeObjects);
        }

        @Override
        protected JsonDeserializer<?> _createWithMerge(boolean mergeArrays, boolean mergeObjects) {
            return new ArrayDeserializer(this, mergeArrays, mergeObjects);
        }

        @Override
        public ArrayNode deserialize(JsonParser p, DeserializationContext ctxt) throws IOException {
            if (p.isExpectedStartArrayToken()) {
                final JsonNodeFactory nodeF = ctxt.getNodeFactory();
                final ArrayNode arrayNode = nodeF.arrayNode();
                _deserializeContainerNoRecursion(p, ctxt, nodeF, new ContainerStack(), arrayNode);
                return arrayNode;
            }
            return (ArrayNode) ctxt.handleUnexpectedToken(ArrayNode.class, p);
        }

        @Override
        public ArrayNode deserialize(JsonParser p, DeserializationContext ctxt, ArrayNode arrayNode) throws IOException {
            if (p.isExpectedStartArrayToken()) {
                _deserializeContainerNoRecursion(p, ctxt, ctxt.getNodeFactory(), new ContainerStack(), arrayNode);
                return arrayNode;
            }
            return (ArrayNode) ctxt.handleUnexpectedToken(ArrayNode.class, p);
        }
    }
}

@SuppressWarnings("serial")
abstract class BaseNodeDeserializer<T extends JsonNode> extends StdDeserializer<T> implements ContextualDeserializer {
    protected final Boolean _supportsUpdates;
    protected final boolean _mergeArrays;
    protected final boolean _mergeObjects;

    public BaseNodeDeserializer(Class<T> vc, Boolean supportsUpdates) {
        super(vc);
        _supportsUpdates = supportsUpdates;
        _mergeArrays = true;
        _mergeObjects = true;
    }

    protected BaseNodeDeserializer(BaseNodeDeserializer<?> base, boolean mergeArrays, boolean mergeObjects) {
        super(base);
        _supportsUpdates = base._supportsUpdates;
        _mergeArrays = mergeArrays;
        _mergeObjects = mergeObjects;
    }

    @Override
    public Object deserializeWithType(JsonParser p, DeserializationContext ctxt, TypeDeserializer typeDeserializer) throws IOException {
        return typeDeserializer.deserializeTypedFromAny(p, ctxt);
    }

    @Override
    public LogicalType logicalType() {
        return LogicalType.Untyped;
    }

    @Override
    public boolean isCachable() {
        return true;
    }

    @Override
    public Boolean supportsUpdate(DeserializationConfig config) {
        return _supportsUpdates;
    }

    @Override
    public JsonDeserializer<?> createContextual(DeserializationContext ctxt, BeanProperty property) {
        final DeserializationConfig cfg = ctxt.getConfig();
        Boolean mergeArr = cfg.getDefaultMergeable(ArrayNode.class);
        Boolean mergeObj = cfg.getDefaultMergeable(ObjectNode.class);
        Boolean mergeNode = cfg.getDefaultMergeable(JsonNode.class);

        final boolean mergeArrays = _shouldMerge(mergeArr, mergeNode);
        final boolean mergeObjects = _shouldMerge(mergeObj, mergeNode);

        if ((mergeArrays != _mergeArrays) || (mergeObjects != _mergeObjects)) {
            return _createWithMerge(mergeArrays, mergeObjects);
        }

        return this;
    }

    private static boolean _shouldMerge(Boolean specificMerge, Boolean generalMerge) {
        if (specificMerge != null) {
            return specificMerge;
        }
        if (generalMerge != null) {
            return generalMerge;
        }
        return true;
    }

    protected abstract JsonDeserializer<?> _createWithMerge(boolean mergeArrays, boolean mergeObjects);

    protected void _handleDuplicateField(JsonParser p, DeserializationContext ctxt, JsonNodeFactory nodeFactory, String fieldName, ObjectNode objectNode, JsonNode oldValue, JsonNode newValue) throws IOException {
        if (ctxt.isEnabled(DeserializationFeature.FAIL_ON_READING_DUP_TREE_KEY)) {
            ctxt.reportInputMismatch(JsonNode.class, "Duplicate field '%s' for `ObjectNode`: not allowed when `DeserializationFeature.FAIL_ON_READING_DUP_TREE_KEY` enabled", fieldName);
        }

        if (ctxt.isEnabled(StreamReadCapability.DUPLICATE_PROPERTIES)) {
            if (oldValue.isArray()) {
                ((ArrayNode) oldValue).add(newValue);
                objectNode.replace(fieldName, oldValue);
            } else {
                ArrayNode arr = nodeFactory.arrayNode();
                arr.add(oldValue);
                arr.add(newValue);
                objectNode.replace(fieldName, arr);
            }
        }
    }

    protected final ObjectNode _deserializeObjectAtName(JsonParser p, DeserializationContext ctxt, final JsonNodeFactory nodeFactory, final ContainerStack stack) throws IOException {
        final ObjectNode node = nodeFactory.objectNode();
        String key = p.currentName();
        for (; key != null; key = p.nextFieldName()) {
            JsonNode value;
            JsonToken t = p.nextToken();
            if (t == null) {
                t = JsonToken.NOT_AVAILABLE;
            }
            switch (t.id()) {
                case JsonTokenId.ID_START_OBJECT:
                    value = _deserializeContainerNoRecursion(p, ctxt, nodeFactory, stack, nodeFactory.objectNode());
                    break;
                case JsonTokenId.ID_START_ARRAY:
                    value = _deserializeContainerNoRecursion(p, ctxt, nodeFactory, stack, nodeFactory.arrayNode());
                    break;
                default:
                    value = _deserializeAnyScalar(p, ctxt);
            }
            JsonNode old = node.replace(key, value);
            if (old != null) {
                _handleDuplicateField(p, ctxt, nodeFactory, key, node, old, value);
            }
        }
        return node;
    }

    protected final JsonNode updateObject(JsonParser p, DeserializationContext ctxt, final ObjectNode node, final ContainerStack stack) throws IOException {
        String key;
        if (p.isExpectedStartObjectToken()) {
            key = p.nextFieldName();
        } else {
            if (!p.hasToken(JsonToken.FIELD_NAME)) {
                return deserialize(p, ctxt);
            }
            key = p.currentName();
        }
        final JsonNodeFactory nodeFactory = ctxt.getNodeFactory();
        for (; key != null; key = p.nextFieldName()) {
            JsonToken t = p.nextToken();
            JsonNode old = node.get(key);
            if (old != null) {
                if (old instanceof ObjectNode) {
                    if ((t == JsonToken.START_OBJECT) && _mergeObjects) {
                        JsonNode newValue = updateObject(p, ctxt, (ObjectNode) old, stack);
                        if (newValue != old) {
                            node.set(key, newValue);
                        }
                        continue;
                    }
                } else if (old instanceof ArrayNode) {
                    if ((t == JsonToken.START_ARRAY) && _mergeArrays) {
                        _deserializeContainerNoRecursion(p, ctxt, nodeFactory, stack, (ArrayNode) old);
                        continue;
                    }
                }
            }
            if (t == null) {
                t = JsonToken.NOT_AVAILABLE;
            }
            JsonNode value;
            switch (t.id()) {
                case JsonTokenId.ID_START_OBJECT:
                    value = _deserializeContainerNoRecursion(p, ctxt, nodeFactory, stack, nodeFactory.objectNode());
                    break;
                case JsonTokenId.ID_START_ARRAY:
                    value = _deserializeContainerNoRecursion(p, ctxt, nodeFactory, stack, nodeFactory.arrayNode());
                    break;
                case JsonTokenId.ID_STRING:
                    value = nodeFactory.textNode(p.getText());
                    break;
                case JsonTokenId.ID_NUMBER_INT:
                    value = _fromInt(p, ctxt, nodeFactory);
                    break;
                case JsonTokenId.ID_TRUE:
                    value = nodeFactory.booleanNode(true);
                    break;
                case JsonTokenId.ID_FALSE:
                    value = nodeFactory.booleanNode(false);
                    break;
                case JsonTokenId.ID_NULL:
                    if (!ctxt.isEnabled(JsonNodeFeature.READ_NULL_PROPERTIES)) {
                        continue;
                    }
                    value = nodeFactory.nullNode();
                    break;
                default:
                    value = _deserializeRareScalar(p, ctxt);
            }
            node.set(key, value);
        }
        return node;
    }

    protected final ContainerNode<?> _deserializeContainerNoRecursion(JsonParser p, DeserializationContext ctxt, JsonNodeFactory nodeFactory, ContainerStack stack, final ContainerNode<?> root) throws IOException {
        ContainerNode<?> curr = root;
        final int intCoercionFeats = ctxt.getDeserializationFeatures() & F_MASK_INT_COERCIONS;
        outer_loop:
        do {
            if (curr instanceof ObjectNode) {
                ObjectNode currObject = (ObjectNode) curr;
                String propName = p.nextFieldName();

                objectLoop:
                for (; propName != null; propName = p.nextFieldName()) {
                    JsonNode value;
                    JsonToken t = p.nextToken();
                    if (t == null) {
                        t = JsonToken.NOT_AVAILABLE;
                    }
                    switch (t.id()) {
                        case JsonTokenId.ID_START_OBJECT: {
                            ObjectNode newOb = nodeFactory.objectNode();
                            JsonNode old = currObject.replace(propName, newOb);
                            if (old != null) {
                                _handleDuplicateField(p, ctxt, nodeFactory, propName, currObject, old, newOb);
                            }
                            stack.push(curr);
                            curr = currObject = newOb;
                            continue objectLoop;
                        }
                        case JsonTokenId.ID_START_ARRAY: {
                            ArrayNode newOb = nodeFactory.arrayNode();
                            JsonNode old = currObject.replace(propName, newOb);
                            if (old != null) {
                                _handleDuplicateField(p, ctxt, nodeFactory, propName, currObject, old, newOb);
                            }
                            stack.push(curr);
                            curr = newOb;
                        }
                        continue outer_loop;
                        case JsonTokenId.ID_ENUM:
                            value = EnumNode.valueOf((Enum<?>) p.getObject());
                            break;
                        case JsonTokenId.ID_STRING:
                            value = nodeFactory.textNode(p.getText());
                            break;
                        case JsonTokenId.ID_NUMBER_INT:
                            value = _fromInt(p, intCoercionFeats, nodeFactory);
                            break;
                        case JsonTokenId.ID_NUMBER_FLOAT:
                            value = _fromFloat(p, ctxt, nodeFactory);
                            break;
                        case JsonTokenId.ID_TRUE:
                            value = nodeFactory.booleanNode(true);
                            break;
                        case JsonTokenId.ID_FALSE:
                            value = nodeFactory.booleanNode(false);
                            break;
                        case JsonTokenId.ID_NULL:
                            if (!ctxt.isEnabled(JsonNodeFeature.READ_NULL_PROPERTIES)) {
                                continue;
                            }
                            value = nodeFactory.nullNode();
                            break;
                        default:
                            value = _deserializeRareScalar(p, ctxt);
                    }
                    JsonNode old = currObject.replace(propName, value);
                    if (old != null) {
                        _handleDuplicateField(p, ctxt, nodeFactory, propName, currObject, old, value);
                    }
                }
            } else {
                final ArrayNode currArray = (ArrayNode) curr;
                arrayLoop:
                while (true) {
                    JsonToken t = p.nextToken();
                    if (t == null) {
                        t = JsonToken.NOT_AVAILABLE;
                    }
                    switch (t.id()) {
                        case JsonTokenId.ID_START_OBJECT:
                            stack.push(curr);
                            curr = nodeFactory.objectNode();
                            currArray.add(curr);
                            continue outer_loop;
                        case JsonTokenId.ID_START_ARRAY:
                            stack.push(curr);
                            curr = nodeFactory.arrayNode();
                            currArray.add(curr);
                            continue outer_loop;
                        case JsonTokenId.ID_END_ARRAY:
                            break arrayLoop;
                        case JsonTokenId.ID_STRING:
                            currArray.add(nodeFactory.textNode(p.getText()));
                            continue arrayLoop;
                        case JsonTokenId.ID_NUMBER_INT:
                            currArray.add(_fromInt(p, intCoercionFeats, nodeFactory));
                            continue arrayLoop;
                        case JsonTokenId.ID_NUMBER_FLOAT:
                            currArray.add(_fromFloat(p, ctxt, nodeFactory));
                            continue arrayLoop;
                        case JsonTokenId.ID_TRUE:
                            currArray.add(nodeFactory.booleanNode(true));
                            continue arrayLoop;
                        case JsonTokenId.ID_FALSE:
                            currArray.add(nodeFactory.booleanNode(false));
                            continue arrayLoop;
                        case JsonTokenId.ID_NULL:
                            currArray.add(nodeFactory.nullNode());
                            continue arrayLoop;
                        case JsonTokenId.ID_ENUM:
                            currArray.add(EnumNode.valueOf((Enum<?>) p.getObject()));
                            continue;
                        default:
                            currArray.add(_deserializeRareScalar(p, ctxt));
                            continue arrayLoop;
                    }
                }
            }
            curr = stack.popOrNull();
        } while (curr != null);
        return root;
    }

    protected final JsonNode _deserializeAnyScalar(JsonParser p, DeserializationContext ctxt) throws IOException {
        final JsonNodeFactory nodeF = ctxt.getNodeFactory();
        switch (p.currentTokenId()) {
            case JsonTokenId.ID_END_OBJECT:
                return nodeF.objectNode();
            case JsonTokenId.ID_STRING:
                return nodeF.textNode(p.getText());
            case JsonTokenId.ID_ENUM:
                return EnumNode.valueOf((Enum<?>) p.getObject());
            case JsonTokenId.ID_NUMBER_INT:
                return _fromInt(p, ctxt, nodeF);
            case JsonTokenId.ID_NUMBER_FLOAT:
                return _fromFloat(p, ctxt, nodeF);
            case JsonTokenId.ID_TRUE:
                return nodeF.booleanNode(true);
            case JsonTokenId.ID_FALSE:
                return nodeF.booleanNode(false);
            case JsonTokenId.ID_NULL:
                return nodeF.nullNode();
            case JsonTokenId.ID_EMBEDDED_OBJECT:
                return _fromEmbedded(p, ctxt);
            default:
        }
        return (JsonNode) ctxt.handleUnexpectedToken(handledType(), p);
    }

    protected final JsonNode _deserializeRareScalar(JsonParser p, DeserializationContext ctxt) throws IOException {
        switch (p.currentTokenId()) {
            case JsonTokenId.ID_END_OBJECT:
                return ctxt.getNodeFactory().objectNode();
            case JsonTokenId.ID_NUMBER_FLOAT:
                return _fromFloat(p, ctxt, ctxt.getNodeFactory());
            case JsonTokenId.ID_EMBEDDED_OBJECT:
                return _fromEmbedded(p, ctxt);
            default:
        }
        return (JsonNode) ctxt.handleUnexpectedToken(handledType(), p);
    }

    protected final JsonNode _fromInt(JsonParser p, int coercionFeatures, JsonNodeFactory nodeFactory) throws IOException {
        if (coercionFeatures != 0) {
            if (DeserializationFeature.USE_BIG_INTEGER_FOR_INTS.enabledIn(coercionFeatures)) {
                return nodeFactory.numberNode(p.getBigIntegerValue());
            }
            return nodeFactory.numberNode(p.getLongValue());
        }
        final JsonParser.NumberType nt = p.getNumberType();
        if (nt == JsonParser.NumberType.INT) {
            return nodeFactory.numberNode(p.getIntValue());
        }
        if (nt == JsonParser.NumberType.LONG) {
            return nodeFactory.numberNode(p.getLongValue());
        }
        return nodeFactory.numberNode(p.getBigIntegerValue());
    }

    protected final JsonNode _fromInt(JsonParser p, DeserializationContext ctxt, JsonNodeFactory nodeFactory) throws IOException {
        JsonParser.NumberType nt;
        int feats = ctxt.getDeserializationFeatures();
        if ((feats & F_MASK_INT_COERCIONS) != 0) {
            if (DeserializationFeature.USE_BIG_INTEGER_FOR_INTS.enabledIn(feats)) {
                nt = JsonParser.NumberType.BIG_INTEGER;
            } else if (DeserializationFeature.USE_LONG_FOR_INTS.enabledIn(feats)) {
                nt = JsonParser.NumberType.LONG;
            } else {
                nt = p.getNumberType();
            }
        } else {
            nt = p.getNumberType();
        }
        if (nt == JsonParser.NumberType.INT) {
            return nodeFactory.numberNode(p.getIntValue());
        }
        if (nt == JsonParser.NumberType.LONG) {
            return nodeFactory.numberNode(p.getLongValue());
        }
        return nodeFactory.numberNode(p.getBigIntegerValue());
    }

    protected final JsonNode _fromFloat(JsonParser p, DeserializationContext ctxt, JsonNodeFactory nodeFactory) throws IOException {
        JsonParser.NumberTypeFP nt = p.getNumberTypeFP();
        if (nt == JsonParser.NumberTypeFP.BIG_DECIMAL) {
            return _fromBigDecimal(ctxt, nodeFactory, p.getDecimalValue());
        }
        if (ctxt.isEnabled(DeserializationFeature.USE_BIG_DECIMAL_FOR_FLOATS)) {
            if (p.isNaN()) {
                if (ctxt.isEnabled(JsonNodeFeature.FAIL_ON_NAN_TO_BIG_DECIMAL_COERCION)) {
                    return (JsonNode) ctxt.handleWeirdNumberValue(handledType(), p.getDoubleValue(), "Cannot convert NaN into BigDecimal");
                }
                return nodeFactory.numberNode(p.getDoubleValue());
            }
            return _fromBigDecimal(ctxt, nodeFactory, p.getDecimalValue());
        }
        if (nt == JsonParser.NumberTypeFP.FLOAT32) {
            return nodeFactory.numberNode(p.getFloatValue());
        }
        return nodeFactory.numberNode(p.getDoubleValue());
    }

    protected final JsonNode _fromBigDecimal(DeserializationContext ctxt, JsonNodeFactory nodeFactory, BigDecimal bigDec) {
        boolean normalize;
        final DatatypeFeatures dtf = ctxt.getDatatypeFeatures();
        if (dtf.isExplicitlySet(JsonNodeFeature.STRIP_TRAILING_BIGDECIMAL_ZEROES)) {
            normalize = dtf.isEnabled(JsonNodeFeature.STRIP_TRAILING_BIGDECIMAL_ZEROES);
        } else {
            normalize = nodeFactory.willStripTrailingBigDecimalZeroes();
        }
        if (normalize) {
            try {
                bigDec = bigDec.stripTrailingZeros();
            } catch (ArithmeticException e) {
            }
        }
        return nodeFactory.numberNode(bigDec);
    }

    protected final JsonNode _fromEmbedded(JsonParser p, DeserializationContext ctxt) throws IOException {
        final JsonNodeFactory nodeF = ctxt.getNodeFactory();
        final Object ob = p.getEmbeddedObject();
        if (ob == null) {
            return nodeF.nullNode();
        }
        Class<?> type = ob.getClass();
        if (type == byte[].class) {
            return nodeF.binaryNode((byte[]) ob);
        }
        if (ob instanceof RawValue) {
            return nodeF.rawValueNode((RawValue) ob);
        }
        if (ob instanceof JsonNode) {
            return (JsonNode) ob;
        }
        return nodeF.pojoNode(ob);
    }

    @SuppressWarnings("rawtypes")
    final static class ContainerStack {
        private ContainerNode[] _stack;
        private int _top, _end;

        public ContainerStack() {
        }

        public int size() {
            return _top;
        }

        public void push(ContainerNode node) {
            if (_top < _end) {
                _stack[_top++] = node;
                return;
            }
            if (_stack == null) {
                _end = 10;
                _stack = new ContainerNode[_end];
            } else {
                _end += Math.min(4000, Math.max(20, _end >> 1));
                _stack = Arrays.copyOf(_stack, _end);
            }
            _stack[_top++] = node;
        }

        public ContainerNode popOrNull() {
            if (_top == 0) {
                return null;
            }
            return _stack[--_top];
        }
    }
}
